// SPDX-License-Identifier: GPL-2.0-only/* * Copyright (C) 2007 Jens Axboe <jens.axboe@oracle.com> * * Scatterlist handling helpers. */#include <linux/export.h>#include <linux/slab.h>#include <linux/scatterlist.h>#include <linux/highmem.h>#include <linux/kmemleak.h>#include <linux/bvec.h>#include <linux/uio.h>#include <linux/folio_queue.h> /** * sg_nents - return total count of entries in scatterlist * @sg:		The scatterlist * * Description: * Allows to know how many entries are in sg, taking into account * chaining as well * **/int sg_nents(struct scatterlist *sg){	int nents;	for (nents = 0; sg; sg = sg_next(sg))		nents++;	return nents;}EXPORT_SYMBOL(sg_nents); /** * sg_nents_for_len - return total count of entries in scatterlist *                    needed to satisfy the supplied length * @sg:		The scatterlist * @len:	The total required length * * Description: * Determines the number of entries in sg that are required to meet * the supplied length, taking into account chaining as well * * Returns: *   the number of sg entries needed, negative error on failure * **/int sg_nents_for_len(struct scatterlist *sg, u64 len){	int nents;	u64 total; 	if (!len)		return 0; 	for (nents = 0, total = 0; sg; sg = sg_next(sg)) {		nents++;		total += sg->length;		if (total >= len)			return nents;	} 	return -EINVAL;}EXPORT_SYMBOL(sg_nents_for_len); /** * sg_nents_for_dma - return the count of DMA-capable entries in scatterlist * @sgl:	The scatterlist * @sglen:	The current number of entries * @len:	The maximum length of DMA-capable block * * Description: * Determines the number of entries in @sgl which would be permitted in * DMA-capable transfer if list had been split accordingly, taking into * account chaining as well. * * Returns: *   the number of sgl entries needed * **/int sg_nents_for_dma(struct scatterlist *sgl, unsigned int sglen, size_t len){	struct scatterlist *sg;	int i, nents = 0; 	for_each_sg(sgl, sg, sglen, i)		nents += DIV_ROUND_UP(sg_dma_len(sg), len);	return nents;}EXPORT_SYMBOL(sg_nents_for_dma); /** * sg_last - return the last scatterlist entry in a list * @sgl:	First entry in the scatterlist * @nents:	Number of entries in the scatterlist * * Description: *   Should only be used casually, it (currently) scans the entire list *   to get the last entry. * *   Note that the @sgl pointer passed in need not be the first one, *   the important bit is that @nents denotes the number of entries that *   exist from @sgl. * **/struct scatterlist *sg_last(struct scatterlist *sgl, unsigned int nents){	struct scatterlist *sg, *ret = NULL;	unsigned int i; 	for_each_sg(sgl, sg, nents, i)		ret = sg; 	BUG_ON(!sg_is_last(ret));	return ret;}EXPORT_SYMBOL(sg_last); /** * sg_init_table - Initialize SG table * @sgl:	   The SG table * @nents:	   Number of entries in table * * Notes: *   If this is part of a chained sg table, sg_mark_end() should be *   used only on the last table part. * **/void sg_init_table(struct scatterlist *sgl, unsigned int nents){	memset(sgl, 0, sizeof(*sgl) * nents);	sg_init_marker(sgl, nents);}EXPORT_SYMBOL(sg_init_table); /** * sg_init_one - Initialize a single entry sg list * @sg:		 SG entry * @buf:	 Virtual address for IO * @buflen:	 IO length * **/void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen){	sg_init_table(sg, 1);	sg_set_buf(sg, buf, buflen);}EXPORT_SYMBOL(sg_init_one); /* * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree * helpers. */static struct scatterlist *sg_kmalloc(unsigned int nents, gfp_t gfp_mask){	if (nents == SG_MAX_SINGLE_ALLOC) {		/*		 * Kmemleak doesn't track page allocations as they are not		 * commonly used (in a raw form) for kernel data structures.		 * As we chain together a list of pages and then a normal		 * kmalloc (tracked by kmemleak), in order to for that last		 * allocation not to become decoupled (and thus a		 * false-positive) we need to inform kmemleak of all the		 * intermediate allocations.		 */		void *ptr = (void *) __get_free_page(gfp_mask);		kmemleak_alloc(ptr, PAGE_SIZE, 1, gfp_mask);		return ptr;	} else		return kmalloc_objs(struct scatterlist, nents, gfp_mask);} static void sg_kfree(struct scatterlist *sg, unsigned int nents){	if (nents == SG_MAX_SINGLE_ALLOC) {		kmemleak_free(sg);		free_page((unsigned long) sg);	} else		kfree(sg);} /** * __sg_free_table - Free a previously mapped sg table * @table:	The sg table header to use * @max_ents:	The maximum number of entries per single scatterlist * @nents_first_chunk: Number of entries int the (preallocated) first * 	scatterlist chunk, 0 means no such preallocated first chunk * @free_fn:	Free function * @num_ents:	Number of entries in the table * *  Description: *    Free an sg table previously allocated and setup with *    __sg_alloc_table().  The @max_ents value must be identical to *    that previously used with __sg_alloc_table(). * **/void __sg_free_table(struct sg_table *table, unsigned int max_ents,		     unsigned int nents_first_chunk, sg_free_fn *free_fn,		     unsigned int num_ents){	struct scatterlist *sgl, *next;	unsigned curr_max_ents = nents_first_chunk ?: max_ents; 	if (unlikely(!table->sgl))		return; 	sgl = table->sgl;	while (num_ents) {		unsigned int alloc_size = num_ents;		unsigned int sg_size; 		/*		 * If we have more than max_ents segments left,		 * then assign 'next' to the sg table after the current one.		 * sg_size is then one less than alloc size, since the last		 * element is the chain pointer.		 */		if (alloc_size > curr_max_ents) {			next = sg_chain_ptr(&sgl[curr_max_ents - 1]);			alloc_size = curr_max_ents;			sg_size = alloc_size - 1;		} else {			sg_size = alloc_size;			next = NULL;		} 		num_ents -= sg_size;		if (nents_first_chunk)			nents_first_chunk = 0;		else			free_fn(sgl, alloc_size);		sgl = next;		curr_max_ents = max_ents;	} 	table->sgl = NULL;}EXPORT_SYMBOL(__sg_free_table); /** * sg_free_append_table - Free a previously allocated append sg table. * @table:	 The mapped sg append table header * **/void sg_free_append_table(struct sg_append_table *table){	__sg_free_table(&table->sgt, SG_MAX_SINGLE_ALLOC, 0, sg_kfree,			table->total_nents);}EXPORT_SYMBOL(sg_free_append_table);  /** * sg_free_table - Free a previously allocated sg table * @table:	The mapped sg table header * **/void sg_free_table(struct sg_table *table){	__sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree,			table->orig_nents);}EXPORT_SYMBOL(sg_free_table); /** * __sg_alloc_table - Allocate and initialize an sg table with given allocator * @table:	The sg table header to use * @nents:	Number of entries in sg list * @max_ents:	The maximum number of entries the allocator returns per call * @first_chunk: first SGL if preallocated (may be %NULL) * @nents_first_chunk: Number of entries in the (preallocated) first * 	scatterlist chunk, 0 means no such preallocated chunk provided by user * @gfp_mask:	GFP allocation mask * @alloc_fn:	Allocator to use * * Description: *   This function returns a @table @nents long. The allocator is *   defined to return scatterlist chunks of maximum size @max_ents. *   Thus if @nents is bigger than @max_ents, the scatterlists will be *   chained in units of @max_ents. * * Notes: *   If this function returns non-0 (eg failure), the caller must call *   __sg_free_table() to cleanup any leftover allocations. * **/int __sg_alloc_table(struct sg_table *table, unsigned int nents,		     unsigned int max_ents, struct scatterlist *first_chunk,		     unsigned int nents_first_chunk, gfp_t gfp_mask,		     sg_alloc_fn *alloc_fn){	struct scatterlist *sg, *prv;	unsigned int left;	unsigned curr_max_ents = nents_first_chunk ?: max_ents;	unsigned prv_max_ents; 	memset(table, 0, sizeof(*table)); 	if (nents == 0)		return -EINVAL;#ifdef CONFIG_ARCH_NO_SG_CHAIN	if (WARN_ON_ONCE(nents > max_ents))		return -EINVAL;#endif 	left = nents;	prv = NULL;	do {		unsigned int sg_size, alloc_size = left; 		if (alloc_size > curr_max_ents) {			alloc_size = curr_max_ents;			sg_size = alloc_size - 1;		} else			sg_size = alloc_size; 		left -= sg_size; 		if (first_chunk) {			sg = first_chunk;			first_chunk = NULL;		} else {			sg = alloc_fn(alloc_size, gfp_mask);		}		if (unlikely(!sg)) {			/*			 * Adjust entry count to reflect that the last			 * entry of the previous table won't be used for			 * linkage.  Without this, sg_kfree() may get			 * confused.			 */			if (prv)				table->nents = ++table->orig_nents; 			return -ENOMEM;		} 		sg_init_table(sg, alloc_size);		table->nents = table->orig_nents += sg_size; 		/*		 * If this is the first mapping, assign the sg table header.		 * If this is not the first mapping, chain previous part.		 */		if (prv)			sg_chain(prv, prv_max_ents, sg);		else			table->sgl = sg; 		/*		 * If no more entries after this one, mark the end		 */		if (!left)			sg_mark_end(&sg[sg_size - 1]); 		prv = sg;		prv_max_ents = curr_max_ents;		curr_max_ents = max_ents;	} while (left); 	return 0;}EXPORT_SYMBOL(__sg_alloc_table); /** * sg_alloc_table - Allocate and initialize an sg table * @table:	The sg table header to use * @nents:	Number of entries in sg list * @gfp_mask:	GFP allocation mask * *  Description: *    Allocate and initialize an sg table. If @nents is larger than *    SG_MAX_SINGLE_ALLOC a chained sg table will be setup. * **/int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask){	int ret; 	ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC,			       NULL, 0, gfp_mask, sg_kmalloc);	if (unlikely(ret))		sg_free_table(table);	return ret;}EXPORT_SYMBOL(sg_alloc_table); static struct scatterlist *get_next_sg(struct sg_append_table *table,				       struct scatterlist *cur,				       unsigned long needed_sges,				       gfp_t gfp_mask){	struct scatterlist *new_sg, *next_sg;	unsigned int alloc_size; 	if (cur) {		next_sg = sg_next(cur);		/* Check if last entry should be keeped for chainning */		if (!sg_is_last(next_sg) || needed_sges == 1)			return next_sg;	} 	alloc_size = min_t(unsigned long, needed_sges, SG_MAX_SINGLE_ALLOC);	new_sg = sg_kmalloc(alloc_size, gfp_mask);	if (!new_sg)		return ERR_PTR(-ENOMEM);	sg_init_table(new_sg, alloc_size);	if (cur) {		table->total_nents += alloc_size - 1;		__sg_chain(next_sg, new_sg);	} else {		table->sgt.sgl = new_sg;		table->total_nents = alloc_size;	}	return new_sg;} static bool pages_are_mergeable(struct page *a, struct page *b){	if (page_to_pfn(a) != page_to_pfn(b) + 1)		return false;	if (!zone_device_pages_have_same_pgmap(a, b))		return false;	return true;} /** * sg_alloc_append_table_from_pages - Allocate and initialize an append sg *                                    table from an array of pages * @sgt_append:  The sg append table to use * @pages:       Pointer to an array of page pointers * @n_pages:     Number of pages in the pages array * @offset:      Offset from start of the first page to the start of a buffer * @size:        Number of valid bytes in the buffer (after offset) * @max_segment: Maximum size of a scatterlist element in bytes * @left_pages:  Left pages caller have to set after this call * @gfp_mask:	 GFP allocation mask * * Description: *    In the first call it allocate and initialize an sg table from a list of *    pages, else reuse the scatterlist from sgt_append. Contiguous ranges of *    the pages are squashed into a single scatterlist entry up to the maximum *    size specified in @max_segment.  A user may provide an offset at a start *    and a size of valid data in a buffer specified by the page array. The *    returned sg table is released by sg_free_append_table * * Returns: *   0 on success, negative error on failure * * Notes: *   If this function returns non-0 (eg failure), the caller must call *   sg_free_append_table() to cleanup any leftover allocations. * *   In the fist call, sgt_append must by initialized. */int sg_alloc_append_table_from_pages(struct sg_append_table *sgt_append,		struct page **pages, unsigned int n_pages, unsigned int offset,		unsigned long size, unsigned int max_segment,		unsigned int left_pages, gfp_t gfp_mask){	unsigned int chunks, cur_page, seg_len, i, prv_len = 0;	unsigned int added_nents = 0;	struct scatterlist *s = sgt_append->prv;	struct page *last_pg; 	/*	 * The algorithm below requires max_segment to be aligned to PAGE_SIZE	 * otherwise it can overshoot.	 */	max_segment = ALIGN_DOWN(max_segment, PAGE_SIZE);	if (WARN_ON(max_segment < PAGE_SIZE))		return -EINVAL; 	if (IS_ENABLED(CONFIG_ARCH_NO_SG_CHAIN) && sgt_append->prv)		return -EOPNOTSUPP; 	if (sgt_append->prv) {		unsigned long next_pfn; 		if (WARN_ON(offset))			return -EINVAL; 		/* Merge contiguous pages into the last SG */		prv_len = sgt_append->prv->length;		next_pfn = (sg_phys(sgt_append->prv) + prv_len) / PAGE_SIZE;		if (page_to_pfn(pages[0]) == next_pfn) {			last_pg = pfn_to_page(next_pfn - 1);			while (n_pages && pages_are_mergeable(pages[0], last_pg)) {				if (sgt_append->prv->length + PAGE_SIZE > max_segment)					break;				sgt_append->prv->length += PAGE_SIZE;				last_pg = pages[0];				pages++;				n_pages--;			}			if (!n_pages)				goto out;		}	}

Lines 1–500 of 1439. Load more